import random

class Solution:
    def quickSort(self,s):
        return self.help(s,0,len(s)-1)
    def help(self,s,begin,end):
        if begin>end:
            return
        # m = random.randint(begin, end - begin)
        # s[m],s[begin] = s[begin],s[m]
        l,r = begin,end
        d = s[l]
        while l<r:
            while l<r and s[r]>d:
                r-=1
            while l < r and s[l] <= d:
                l += 1
            s[r],s[l] = s[l],s[r]
        s[begin] = s[l]
        s[l] = d
        self.help(s,begin,l-1)
        self.help(s,r+1,end)
        return s








a = [3,5,1,6,12,2,99,0]
s=Solution()
print(s.quickSort(a))


